
/**
 * aggregates relevant data used for pathfinding
 * computes a* path results
 */


//TODO: Create map partitioning function
//TODO: Create node class
//TODO: node connectivity


package ai;
import java.util.*;
import java.awt.*;

import mapData.Coord;
import mapData.CoordCluster;
import mapData.Obstruction;
import mapObjects.Archer;
import mapObjects.Unit;


public class MapNavigator
{
    
	public static final double COST = 1.0;
    private double diagCost = 0.5;
    
    
    //private static int mapWidth;
    //private static int mapHeight;
    protected static ArrayList<Unit> compUnits, plyrUnits;
    protected static ArrayList<Obstruction> obstructions;
    
    public MapNavigator(ArrayList<Unit> comp, ArrayList<Unit> plyr, ArrayList<Obstruction> obs)
    {
        //mapWidth = w;
        //mapHeight = h;
        compUnits = comp;
        plyrUnits = plyr;
        obstructions = obs;
    }
    
    
    
    public void sortLists()
    {
    	Collections.sort(plyrUnits); //needed to ensure binarySearch works
        Collections.sort(compUnits);
    }
    
    
    
    
    public boolean isEmpty(Coord pos)
        //returns true if Coord pos is an available Coord 
    {
        Archer key = new Archer(new Color(0, 0, 0), pos);
        //System.out.println(Collections.binarySearch(compUnits, key));
        //System.out.println(Collections.binarySearch(plyrUnits, key));
        sortLists();
        
        if(Collections.binarySearch(compUnits, key) >= 0) //found match in compUnits
            return false;
        
        if(Collections.binarySearch(plyrUnits, key) >= 0) //found match in plyrUnits
            return false;
        
        
        for(int i = 0; i < obstructions.size(); i++)
        {
            if(obstructions.get(i).isOnBound(pos))
            {
                
                return false;
            }
        }
        
        return true;
    }
    
    public boolean isOnObstruction(Coord pos)
    {
    	for(int i = 0; i < obstructions.size(); i++)
        {
            if(obstructions.get(i).isOnBound(pos))
            {
                
                return true;
            }
        }
    	return false;
    }
    
    /**
     * Checks if CoordCluster is completely contained within obstruction
     * @param pos
     * @returns true if pos is completely contained
     */
    public boolean isOnObstruction(CoordCluster pos)
    {
    	return (isOnObstruction(pos.getBottomRight())&& isOnObstruction(pos.getTopLeft()));
    }
    
    /**
     * Returns first closest tile to origDest 
     * @param origDest original destination
     * @return 
     */
    public Coord findClosestValidTile(Coord origDest)
    {
    	
		ArrayList<Coord> open = new ArrayList<Coord>();
		ArrayList<Coord> closed = new ArrayList<Coord>(20);
		open.add(origDest);
		closed.add(origDest);
		
		
		
		while(true)
		{
		    int size = open.size();
		    
		    for(int j = 0; j < size; j++)
		    {
		    	//sortByMDistance(open, origDest);
				Coord taken = open.remove(0);
				if(findCoord(closed, taken)== -1)
				    closed.add(taken); 
				
				ArrayList<Coord> valid = taken.getUnobstructedNeighbors();
				for(int k = 0; k < valid.size(); k++)
				{
					Coord newCoord = valid.get(k);
				    if(findCoord(closed, newCoord) != -1) //already added
				    {
				    	continue;
				    }
				    else
				    {				    	
						open.add(newCoord); //add to list of to be searched coords											   
				    }				    
				}
				
				
		    }
		    //sortByHDistance(closed, origDest);
		    for(int l = closed.size()-1; l >=0; l--) //search from back because earlier ones are supposedly occupied
		    {
		    	Coord searched = closed.get(l);
		    	
			    if(isEmpty(searched))
				{
					return searched;
				}
		    }
		}
		
		
		
    }
    public int manhattanDistance(Coord a, Coord b)
    {
    	return Math.abs(a.getX()-b.getX()) + Math.abs(a.getY()-b.getY());
    }
    
   
    
    public void sortUnitByMDistance(ArrayList<Unit> open, Coord origDest)
    {
    	final Coord compTo = origDest;
    	
    	class sortUnitsByMDComparator implements Comparator<Unit>
    	{
    		public int compare(Unit u1, Unit u2) //compares u1 to u2
    		{
    			return manhattanDistance(u1.getCoord(), compTo)-manhattanDistance(u2.getCoord(), compTo);
    		}
    	}
    	
    	Collections.sort(open, new sortUnitsByMDComparator());
    }
    
    
    /**
     * 
     * @param range
     * @param curr
     * @return
     */
    public ArrayList<Unit> getEnemyUnitsInRange(int range, Coord curr, Color col)
    {
		ArrayList<Unit> inRange = new ArrayList<Unit>(0);
		if(col.equals(mapData.Map.computer))
		{
			for(int i = 0; i < plyrUnits.size(); i++)
			{
				Unit atI = plyrUnits.get(i);
				if(manhattanDistance(curr, atI.getCoord()) <= range)
				{
					inRange.add(atI);
				}
			}
		}
		else
		{
			for(int i = 0; i < compUnits.size(); i++)
			{
				Unit atI = compUnits.get(i);
				if(manhattanDistance(curr, atI.getCoord()) <= range)
				{
					inRange.add(atI);
				}
			}
		}
		return inRange;
    }
    
    
    /**
     * searches Coord and adds them into a UnitGroup 
     * Unitgroup will check if unit to be added is the right color
     * @param pos, group
     * 
     */
    public void getUnit(Coord pos, UnitGroup group)
    {
    	sortLists();
    	Archer key = new Archer(new Color(0, 0, 0), pos);
        
        
        if(Collections.binarySearch(compUnits, key) >= 0)
        {
            int index = Collections.binarySearch(compUnits, key);
            group.addUnit(compUnits.get(index));
        }
        
        if(Collections.binarySearch(plyrUnits, key) >= 0)
        {
            int index = Collections.binarySearch(plyrUnits, key);
            group.addUnit(plyrUnits.get(index));
        }
	
	
    }
    
    public void getUnit(Coord pos, ArrayList<Unit> list)
    {
	sortLists();
	Archer key = new Archer(new Color(0, 0, 0), pos);
        
        
        if(Collections.binarySearch(compUnits, key) >= 0)
        {
            int index = Collections.binarySearch(compUnits, key);
            list.add(compUnits.get(index));
        }
        
        if(Collections.binarySearch(plyrUnits, key) >= 0)
        {
            int index = Collections.binarySearch(plyrUnits, key);
            list.add(plyrUnits.get(index));
        }
	
	
    }
    
    public Unit getRefToUnit(Coord c)
    {
    	sortLists();
    	Archer key = new Archer(new Color(0, 0, 0), c);
    	Unit out = key;
    	if(Collections.binarySearch(compUnits, key) >= 0)
        {
            int index = Collections.binarySearch(compUnits, key);
            return compUnits.get(index);
        }
        
        if(Collections.binarySearch(plyrUnits, key) >= 0)
        {
            int index = Collections.binarySearch(plyrUnits, key);
            return plyrUnits.get(index);
        }
        return out; //should only be returned if no unit is found
    	
    }
    
    private double heuristic(Coord start, Coord c, Coord goal) //Manhattan Distance
    {
	
    	double xDist = Math.abs(c.getX() - goal.getX());
    	double yDist = Math.abs(c.getY() - goal.getY());	
    	double v1x = c.getX() - start.getX();
    	double v1y = c.getY() - start.getY();
    	double v2x = goal.getX() - c.getX();
    	double v2y = goal.getY() - c.getY();
    	double cross = Math.abs(v2y*v1x-v2x*v1y);
    	return COST*(xDist + yDist) + diagCost*cross;
    	
    	
        //return COST*( xDist + yDist ) + diagCost*(Math.abs(c.getY() - (toGoalSlope*c.getX()+startY)));
        
    }
    
    public Coord getBestNeighborUsingHeurstic(Coord start, Coord curr, Coord goal)
    {
    	ArrayList<Coord> nbrs = curr.getEmptyNeighbors();
    	nbrs.add(0, curr);
    	int indexOfBest = 0;
    	for(int i = 1; i < nbrs.size(); i++)
    	{
    		if(heuristic(start, nbrs.get(indexOfBest), goal)> 
    		heuristic(start, nbrs.get(i), goal))
    		{
    			indexOfBest = i;
    		}
    	}
    	return nbrs.get(indexOfBest);
    }
    
    
    public ArrayList<Coord> bfsPath(Coord start, Coord goal)
    {
	
        ArrayList<Coord> open = new ArrayList<Coord>(40); //lower index = higher priority
        ArrayList<Coord> closed = new ArrayList<Coord>(100); // already evaluated
        ArrayList<Coord> path = new ArrayList<Coord>(60);
        
        
        open.add(start);
        start.parent = start;
        start.costSoFar = 0;
        //open.trimToSize();
        //closed.trimToSize();
        
        while(!open.isEmpty())
        {
        	
            
            Coord best = open.remove(0);
            
            if(best.isEqual(goal) || best.costSoFar > 40)
            {
                //System.out.println("fin");
                path = genPath(start, best);
                path.remove(0);
                return path;
            }
            else
            {
                
                closed.add(best);
                ArrayList<Coord> nbrs = best.getEmptyNeighbors();
                nbrs.trimToSize();
                //System.out.println(nbrs);
                
                 
                for(int i = 0; i < nbrs.size(); i++)
                {
                    Coord successor = nbrs.get(i);
                    if(findCoord(open, successor) < 0 && 
                       findCoord(closed, successor) < 0) //if not generated before
                    {
                        if(open.isEmpty())
                        {
                            open.add(successor);
                        }
                        else //open is not empty
                        {             
                            for(int j = 0; j < open.size(); j++)
                            {
                                if(heuristic(start, open.get(j), goal) > heuristic(start, successor, goal))
                                {
                                    open.add(j, successor);
                                    break;
                                }
                                if(j == open.size() - 1)
                                {
                                    open.add(successor);
                                    break;
                                }
                            }
                        }           
                    }
                    else if(findCoord(open, successor) >=0) //if node is queued already
                    {//replace if better 
                        int index = findCoord(open, successor);
                        /*
                        if(heuristic(start, successor.parent, goal) < heuristic(start, open.get(index).parent, goal))
                        */
                        if(successor.costSoFar <= open.get(index).costSoFar)
                            open.set(index, successor);
                    }
                    else //if node is searched before
                    {//replace if better
                        int index = findCoord(closed, successor);
                        /*
                        if(heuristic(start, successor.parent, goal) < heuristic(start, closed.get(index).parent, goal))*/
                        if(successor.costSoFar <= closed.get(index).costSoFar)
                            closed.set(index, successor);
                    }
                    
                }
            }
            
        }
        return path;
    }
    
    public ArrayList<Coord> genPath(Coord start, Coord goal)
    {
        ArrayList<Coord> path = new ArrayList<Coord>();
        path.trimToSize();
        path.add(goal);
        Coord parent = goal.parent;
        while(!goal.parent.isEqual(start))
        {
            goal = parent;
            parent = goal.parent;
            path.add(goal);
        }
        path.add(start);
        Collections.reverse(path);
        return path;
        
    }     
    
    
    //linear search for identical Coord in an unsorted list
    public int findCoord(ArrayList<Coord> list, Coord key)
    {
    	for(int i = 0; i < list.size(); i++)
    	{
    		if(list.get(i).isEqual(key))
    		{
    			return i;
    		}
    	}
    	return -1;
    	
    }
    
    
    
   
} 





